//矩阵转置（分段定位法）
#include<stdio.h>
#define MaxTerm 100
#define ElemType int

typedef struct Triple
{
    int x,y;     //x是列  y是行
    ElemType e;
}Triple;

typedef struct 
{
    Triple data[MaxTerm];
    int row,col,num;  //row行 col列 num非零元素个数
}TSMatrix,*TSMatrixptr;

void FastTranspose(TSMatrix A,TSMatrix *B)   //初始化阶段
{
    B->num=A.num;
    B->col=A.row;
    B->row=A.col;
    if(B->num==0)
    {
        printf("Error:三元组为空");
        return ;
    }
    //预处理阶段
    int count[B->row];   //统计每行非零元素个数
    int pot[B->row];     //计算每行的定位指针
    for(int i=0;i<B->row;i++)   count[i]=0;       //初始化一下 防止初始随机值导致错误
    for(int i=0;i<B->num;i++)   count[A.data[i].x]++;  //统计A中各列/未来B中各行的非零元素个数
    pot[0]=0;
    for(int j=1;j<B->row;j++)   pot[j]=pot[j-1]+count[j-1];   //计算未来B中各行的定位指针
    //转置阶段
    for(int i=0;i<B->num;i++)
    {
        int j=A.data[i].x;
        int k=pot[j];
        B->data[k].y=j;        //B->data[k].y=A.data[i].x
        B->data[k].x=A.data[i].y;
        B->data[k].e=A.data[i].e;
        pot[j]++;              //继续完成B中相同row值的复制;
    }
}

int main()
{
    TSMatrix A;
    printf("请输入非零元素的个数：");
    scanf("%d",&A.num);
    printf("请输入稀疏矩阵的行数：");
    scanf("%d",&A.row);
    printf("请输入稀疏矩阵的列数：");
    scanf("%d",&A.col);
    printf("请依次输入非零元素的行 列 值：\n");
    for(int i=0;i<A.num;i++)
    {
        scanf("%d %d %d",&A.data[i].y,&A.data[i].x,&A.data[i].e);
    }
    //三元组A未启用num[],pot[]数组;
    TSMatrix B;
    FastTranspose(A,&B);
    printf("转置后三元组的长度：%d\n",B.num);
    printf("转置后稀疏矩阵的行数：%d\n",B.row);
    printf("转置后稀疏矩阵的列数：%d\n",B.col);
    printf("转置后三元组的数据 行 列 值：\n");
    for(int i=0;i<B.num;i++)
    {
        printf("%d %d %d\n",B.data[i].y,B.data[i].x,B.data[i].e);
    }
}
